// # 链表练习题参考答案（C语言实现）

// ```c
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

// 单链表节点定义
typedef struct ListNode {
    int val;
    struct ListNode *next;
} ListNode;

// ======================= 基础题实现 =======================

// 练习1：单链表基本操作

// 创建新节点
ListNode* createNode(int val) {
    ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
    if (newNode == NULL) {
        printf("内存分配失败！\n");
        exit(1);
    }
    newNode->val = val;
    newNode->next = NULL;
    return newNode;
}

// 在链表头部插入节点
ListNode* insertAtHead(ListNode* head, int val) {
    ListNode* newNode = createNode(val);
    newNode->next = head;
    return newNode; // 返回新的头节点
}

// 在链表尾部插入节点
ListNode* insertAtTail(ListNode* head, int val) {
    ListNode* newNode = createNode(val);
    
    // 如果链表为空，直接返回新节点作为头节点
    if (head == NULL) {
        return newNode;
    }
    
    // 找到链表的最后一个节点
    ListNode* current = head;
    while (current->next != NULL) {
        current = current->next;
    }
    
    // 在尾部插入新节点
    current->next = newNode;
    return head;
}

// 遍历并打印链表
void printList(ListNode* head) {
    ListNode* current = head;
    while (current != NULL) {
        printf("%d -> ", current->val);
        current = current->next;
    }
    printf("NULL\n");
}

// 查找指定值的节点
ListNode* findNode(ListNode* head, int val) {
    ListNode* current = head;
    while (current != NULL) {
        if (current->val == val) {
            return current; // 找到节点，返回节点指针
        }
        current = current->next;
    }
    return NULL; // 未找到节点
}

// 删除指定值的节点
ListNode* deleteNode(ListNode* head, int val) {
    // 处理空链表
    if (head == NULL) {
        return NULL;
    }
    
    // 如果头节点就是要删除的节点
    if (head->val == val) {
        ListNode* temp = head;
        head = head->next;
        free(temp);
        return head;
    }
    
    // 查找要删除的节点的前一个节点
    ListNode* current = head;
    while (current->next != NULL && current->next->val != val) {
        current = current->next;
    }
    
    // 如果找到了要删除的节点
    if (current->next != NULL) {
        ListNode* temp = current->next;
        current->next = current->next->next;
        free(temp);
    }
    
    return head;
}

// 释放链表内存
void freeList(ListNode* head) {
    ListNode* temp;
    while (head != NULL) {
        temp = head;
        head = head->next;
        free(temp);
    }
}

// 练习2：链表长度计算
int getListLength(ListNode* head) {
    int length = 0;
    ListNode* current = head;
    
    while (current != NULL) {
        length++;
        current = current->next;
    }
    
    return length;
}

// 练习3：链表元素反转打印（递归实现）
void printListReversed(ListNode* head) {
    if (head == NULL) {
        return;
    }
    
    printListReversed(head->next);
    printf("%d ", head->val);
}

// ======================= 提高题实现 =======================

// 练习4：单链表反转
ListNode* reverseList(ListNode* head) {
    ListNode* prev = NULL;
    ListNode* current = head;
    ListNode* next = NULL;
    
    while (current != NULL) {
        // 保存下一个节点
        next = current->next;
        // 反转当前节点的指针
        current->next = prev;
        // 移动指针
        prev = current;
        current = next;
    }
    
    // prev现在指向新的头节点
    return prev;
}

// 练习5：链表中环的检测（快慢指针法）
bool hasCycle(ListNode* head) {
    if (head == NULL || head->next == NULL) {
        return false; // 空链表或只有一个节点，不可能有环
    }
    
    ListNode* slow = head; // 慢指针，每次移动一步
    ListNode* fast = head; // 快指针，每次移动两步
    
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;       // 慢指针移动一步
        fast = fast->next->next; // 快指针移动两步
        
        if (slow == fast) {      // 如果快慢指针相遇，说明有环
            return true;
        }
    }
    
    return false; // 快指针到达链表尾部，说明没有环
}

// 练习6：删除链表中的倒数第N个节点
ListNode* removeNthFromEnd(ListNode* head, int n) {
    // 创建虚拟头节点，简化边界情况处理
    ListNode* dummy = createNode(0);
    dummy->next = head;
    
    ListNode* fast = dummy;
    ListNode* slow = dummy;
    
    // 快指针先移动n+1步
    for (int i = 0; i <= n; i++) {
        if (fast == NULL) {
            // n大于链表长度的情况
            free(dummy);
            return head;
        }
        fast = fast->next;
    }
    
    // 同时移动快慢指针，直到快指针到达链表尾部
    while (fast != NULL) {
        slow = slow->next;
        fast = fast->next;
    }
    
    // 此时slow指向待删除节点的前一个节点
    ListNode* temp = slow->next;
    slow->next = slow->next->next;
    free(temp);
    
    // 保存新的头节点
    head = dummy->next;
    free(dummy);
    
    return head;
}

// 练习7：合并两个有序链表
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    // 创建虚拟头节点
    ListNode* dummy = createNode(0);
    ListNode* tail = dummy;
    
    // 比较两个链表的节点，将较小的节点添加到新链表
    while (l1 != NULL && l2 != NULL) {
        if (l1->val <= l2->val) {
            tail->next = l1;
            l1 = l1->next;
        } else {
            tail->next = l2;
            l2 = l2->next;
        }
        tail = tail->next;
    }
    
    // 将剩余的节点添加到新链表
    if (l1 != NULL) {
        tail->next = l1;
    } else {
        tail->next = l2;
    }
    
    // 保存新的头节点并释放虚拟头节点
    ListNode* head = dummy->next;
    free(dummy);
    
    return head;
}

// ======================= 挑战题实现 =======================

// 练习8：链表的中间节点
ListNode* middleNode(ListNode* head) {
    ListNode* slow = head;
    ListNode* fast = head;
    
    // 快指针每次移动两步，慢指针每次移动一步
    // 当快指针到达链表尾部时，慢指针正好指向链表的中间节点
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
    }
    
    return slow;
}

// 示例主函数，演示基础操作
int main() {
    ListNode* head = NULL;
    
    // 测试基本操作
    printf("===== 测试基本操作 =====\n");
    head = insertAtHead(head, 3);
    head = insertAtHead(head, 2);
    head = insertAtHead(head, 1);
    head = insertAtTail(head, 4);
    head = insertAtTail(head, 5);
    
    printf("链表内容: ");
    printList(head);
    
    printf("链表长度: %d\n", getListLength(head));
    
    printf("反转打印: ");
    printListReversed(head);
    printf("\n");
    
    // 测试反转链表
    printf("\n===== 测试反转链表 =====\n");
    head = reverseList(head);
    printf("反转后的链表: ");
    printList(head);
    
    // 测试删除节点
    printf("\n===== 测试删除节点 =====\n");
    head = deleteNode(head, 3);
    printf("删除值为3的节点后: ");
    printList(head);
    
    // 测试删除倒数第N个节点
    printf("\n===== 测试删除倒数第2个节点 =====\n");
    head = removeNthFromEnd(head, 2);
    printf("删除后: ");
    printList(head);
    
    // 测试中间节点
    printf("\n===== 测试中间节点 =====\n");
    ListNode* mid = middleNode(head);
    printf("中间节点的值: %d\n", mid->val);
    
    // 合并两个有序链表测试
    printf("\n===== 测试合并两个有序链表 =====\n");
    ListNode* l1 = NULL;
    ListNode* l2 = NULL;
    
    l1 = insertAtTail(l1, 1);
    l1 = insertAtTail(l1, 3);
    l1 = insertAtTail(l1, 5);
    
    l2 = insertAtTail(l2, 2);
    l2 = insertAtTail(l2, 4);
    l2 = insertAtTail(l2, 6);
    
    printf("链表1: ");
    printList(l1);
    printf("链表2: ");
    printList(l2);
    
    ListNode* merged = mergeTwoLists(l1, l2);
    printf("合并后的链表: ");
    printList(merged);
    
    // 释放内存
    freeList(head);
    // 注意：merged已经包含了l1和l2的节点，所以不需要单独释放l1和l2
    freeList(merged);
    
    return 0;
}
// ```

// ## 代码说明

// 1. **基础数据结构**：定义了单链表节点结构体 `ListNode`，包含值和指向下一个节点的指针。

// 2. **基础操作函数**：
//    - `createNode`：创建新节点
//    - `insertAtHead`：在链表头部插入节点
//    - `insertAtTail`：在链表尾部插入节点
//    - `printList`：遍历并打印链表
//    - `findNode`：查找指定值的节点
//    - `deleteNode`：删除指定值的节点
//    - `freeList`：释放链表内存

// 3. **练习题解答**：
//    - 练习2（链表长度计算）：`getListLength`
//    - 练习3（反转打印）：`printListReversed`（递归实现）
//    - 练习4（单链表反转）：`reverseList`（迭代实现）
//    - 练习5（环检测）：`hasCycle`（快慢指针法）
//    - 练习6（删除倒数第N个节点）：`removeNthFromEnd`（双指针法）
//    - 练习7（合并有序链表）：`mergeTwoLists`（双指针法）
//    - 练习8（中间节点）：`middleNode`（快慢指针法）

// 4. **主函数**：提供了示例代码，演示如何使用这些函数。

// ## 使用建议

// 1. 将此代码保存为 `.c` 文件并使用C编译器编译运行
// 2. 可以根据需要修改主函数中的测试用例
// 3. 对于未实现的挑战题（如练习9、10、11），可以参考已实现的函数自行完成
// 4. 实际练习时，建议先尝试独立解决问题，再参考此答案

// 注意：代码中使用了动态内存分配，请确保正确释放内存以避免内存泄漏。